package com.leetcode.partition3;

import java.util.PriorityQueue;
import java.util.Set;
import java.util.TreeSet;

/**
 * @author `RKC`
 * @date 2021/8/5 8:40
 */
@SuppressWarnings("ALL")
public class LC264丑数2 {

    public static int nthUglyNumber(int n) {
        return dynamicProgramming(n);
    }

    public static void main(String[] args) {
        System.out.println(nthUglyNumber(10));
    }

    private static int dynamicProgramming(int n) {
        long[] dp = new long[n + 1];
        dp[1] = 1;
        int i2 = 1, i3 = 1, i5 = 1;
        for (int i = 2; i < dp.length; i++) {
            long v2 = dp[i2] * 2, v3 = dp[i3] * 3, v5 = dp[i5] * 5;
            dp[i] = Math.min(Math.min(v2, v3), v5);
            //进行去重
            if (v2 == dp[i]) i2++;
            if (v3 == dp[i]) i3++;
            if (v5 == dp[i]) i5++;
        }
        return (int) dp[n];
    }

    private static int setSolution(int n) {
        TreeSet<Long> set = new TreeSet<>();        //使用TreeSet保证顺序，每次取出的第一个元素都是最小的
        long result = 1L;
        set.add(1L);
        for (int i = 1; i <= n; i++) {
            set.add(result * 2);
            set.add(result * 3);
            set.add(result * 5);
            result = set.pollFirst();
        }
        System.out.println(set);
        return Math.toIntExact(result);
    }

    private static int priorityQueue(int n) {
        PriorityQueue<Long> heap = new PriorityQueue<>();
        Set<Long> set = new TreeSet<>();
        heap.add(1L);
        set.add(1L);
        int[] factors = {2, 3, 5};
        long result = 1L;
        for (int i = 0; i < n; i++) {
            result = heap.poll();
            for (int factor : factors) {
                Long number = factor * result;
                if (set.contains(number)) continue;
                heap.add(number);
                set.add(number);
            }
        }
        System.out.println(set);
        return Math.toIntExact(result);
    }
}
